package tree.AVLTree;

/**
 * 2021/9/30 明天国庆节
 * 平衡二叉树，如果数组为{1,2,3,4,5,6,7} 那么数据都在右子树的右子节点上，就像一个链表。没有树的优势
 * 于是我们要平衡左右二棵树。使得左右二棵树的高度的绝对值 0<=h<2
 */
public class AVL {
    public static void main(String[] args) {
        int[] arr = {4, 3, 6, 5, 7, 8}; // 单旋转能够解决平衡问题  这个example
        int[] doubleRotate = {10,12,7,6,8,9,1,2,3};
        AVL avl2 = new AVL();
        avl2.binarySortTree(doubleRotate);
        System.out.println("此为多旋转的例子");
        avl2.infixOrder();
        System.out.println(avl2.getLeftHeight());
        System.out.println(avl2.getRightHeight());
        System.out.println(avl2.getRoot());
        System.out.println("以下是单旋转 例子加验证");
        AVL avl = new AVL();
        avl.binarySortTree(arr);
        avl.infixOrder();
        System.out.println(avl.getLeftHeight());
        System.out.println(avl.getRightHeight());
        System.out.println(avl.getRoot());
    }

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public void add(int value) {
        if (root == null) {
            root = new Node(value);
            return;
        }
        root.add(new Node(value));
    }

    public void binarySortTree(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
            doubleRotate();
        }

    }

    public void infixOrder() {
        root.infixOrder();
    }

    public int getLeftHeight() {
        return root.getLeftHeight();
    }

    public int getRightHeight() {
        return root.getRightHeight();
    }

    /**
     * 单旋转,当右边高度与左边高度差2时候 进行一个旋转，左旋还是右旋看那边低 。
     * 能够处理的情况为： LL / RR 即 左子树的左子树突出
     * 后来我有一个疑问：就是当节点非常多多时候，这个时候也是旋转root吗？ 答案是yes！
     */
    public void singleRotate() {
        // 进行左旋
        if (getRightHeight() - getLeftHeight() > 1) {
            Node t = root.getRight();
            root.setRight(t.getLeft());
            t.setLeft(root);
            setRoot(t);
            return;
        }
        // 进行右旋
        if (getLeftHeight() - getRightHeight() > 1) {
            Node t = root.getLeft();
            root.setLeft(t.getRight());
            t.setRight(root);
            setRoot(t);
        }
    }
    /**
     * 双旋转，当左右高度差为2，并且情况为：LR & RL 对应的左子树右突出 ···
     * 和上面一样，旋转的位置永远是根节点的左或者右
     */
    public void doubleRotate() {
        if (getRightHeight() - getLeftHeight() > 1) {
            // LL
            if (root.getRight().getLeftHeight()-root.getRight().getRightHeight()>0){ // 判断
                Node temp = root.getRight();
                Node t = temp.getLeft();
                temp.setRight(temp);
                t.setRight(temp);
                root.setRight(t);
            }
            singleRotate();
            return;
        }
        if (getLeftHeight() - getRightHeight() > 1) {
            // LR
           if (root.getRight().getRightHeight()-root.getRight().getLeftHeight()>0){
               Node temp = root.getLeft();
               Node t = temp.getRight();
               temp.setRight(t.getLeft());  // 最小的都比你大
               t.setLeft(temp);
               root.setLeft(t);
           }
            singleRotate();
        }
    }
}

